home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / language / embedded / m68k / cc68k.arc / ANALYZE.C next >
C/C++ Source or Header  |  1986-10-28  |  17KB  |  486 lines
  1. #include        "stdio.h"
  2. #include        "c.h"
  3. #include        "expr.h"
  4. #include        "gen.h"
  5. #include        "cglbdec.h"
  6.  
  7. /*
  8.  *    68000 C compiler
  9.  *
  10.  *    Copyright 1984, 1985, 1986 Matthew Brandt.
  11.  *  all commercial rights reserved.
  12.  *
  13.  *    This compiler is intended as an instructive tool for personal use. Any
  14.  *    use for profit without the written consent of the author is prohibited.
  15.  *
  16.  *    This compiler may be distributed freely for non-commercial use as long
  17.  *    as this notice stays intact. Please forward any enhancements or question
  18. s
  19.  *    to:
  20.  *
  21.  *        Matthew Brandt
  22.  *        Box 920337
  23.  *        Norcross, Ga 30092
  24.  */
  25.  
  26. extern struct amode     push[], pop[];
  27.  
  28. /*  External function declarations:             */
  29.  
  30. extern struct amode *gen_expr   ();
  31. extern struct amode *makedreg   ();
  32. extern struct amode *makeareg   ();
  33. /*
  34.  *      this module will step through the parse tree and find all
  35.  *      optimizable expressions. at present these expressions are
  36.  *      limited to expressions that are valid throughout the scope
  37.  *      of the function. the list of optimizable expressions is:
  38.  *
  39.  *              constants
  40.  *              global and static addresses
  41.  *              auto addresses
  42.  *              contents of auto addresses.
  43.  *
  44.  *      contents of auto addresses are valid only if the address is
  45.  *      never referred to without dereferencing.
  46.  *
  47.  *      scan will build a list of optimizable expressions which
  48.  *      opt1 will replace during the second optimization pass.
  49.  */
  50.  
  51. static struct cse       *olist;         /* list of optimizable expressions */
  52.  
  53. int equalnode(node1, node2)
  54. /*
  55.  *      equalnode will return 1 if the expressions pointed to by
  56.  *      node1 and node2 are equivalent.
  57.  */
  58. struct enode    *node1, *node2;
  59. {       if( node1 == 0 || node2 == 0 )
  60.                 return 0;
  61.         if( node1->nodetype != node2->nodetype )
  62.                 return 0;
  63.         if( (node1->nodetype == en_icon || node1->nodetype == en_labcon ||
  64.             node1->nodetype == en_nacon || node1->nodetype == en_autocon) &&
  65.             node1->v.i == node2->v.i )
  66.                 return 1;
  67.         if( lvalue(node1) && equalnode(node1->v.p[0], node2->v.p[0]) )
  68.                 return 1;
  69.         return 0;
  70. }
  71.  
  72. struct cse      *searchnode(node)
  73. /*
  74.  *      searchnode will search the common expression table for an entry
  75.  *      that matches the node passed and return a pointer to it.
  76.  */
  77. struct enode    *node;
  78. {       struct cse      *csp;
  79.         csp = olist;
  80.         while( csp != 0 ) {
  81.                 if( equalnode(node,csp->exp) )
  82.                         return csp;
  83.                 csp = csp->next;
  84.                 }
  85.         return 0;
  86. }
  87.  
  88. struct enode    *copynode(node)
  89. /*
  90.  *      copy the node passed into a new enode so it wont get
  91.  *      corrupted during substitution.
  92.  */
  93. struct enode    *node;
  94. {       struct enode    *temp;
  95.         if( node == 0 )
  96.                 return 0;
  97.         temp = (struct enode *)xalloc(sizeof(struct enode));
  98.         temp->nodetype = node->nodetype;
  99.         temp->v.p[0] = node->v.p[0];
  100.         temp->v.p[1] = node->v.p[1];
  101.         return temp;
  102. }
  103.  
  104. struct cse *enternode(node,duse)
  105. /*
  106.  *      enternode will enter a reference to an expression node into the
  107.  *      common expression table. duse is a flag indicating whether or not
  108.  *      this reference will be dereferenced.
  109.  */
  110. struct enode    *node;
  111. int             duse;
  112. {       struct cse      *csp;
  113.         if( (csp = searchnode(node)) == 0 ) {   /* add to tree */
  114.                 csp =(struct cse *)xalloc(sizeof(struct cse));
  115.                 csp->next = olist;
  116.                 csp->uses = 1;
  117.                 csp->duses = (duse != 0);
  118.                 csp->exp = copynode(node);
  119.                 csp->voidf = 0;
  120.                 olist = csp;
  121.                 return csp;
  122.                 }
  123.         ++(csp->uses);
  124.         if( duse )
  125.                 ++(csp->duses);
  126.         return csp;
  127. }
  128.  
  129. struct cse      *voidauto(node)
  130. /*
  131.  *      voidauto will void an auto dereference node which points to
  132.  *      the same auto constant as node.
  133.  */
  134. struct enode    *node;
  135. {       struct cse      *csp;
  136.         csp = olist;
  137.         while( csp != 0 ) {
  138.                 if( lvalue(csp->exp) && equalnode(node,csp->exp->v.p[0]) ) {
  139.                         if( csp->voidf )
  140.                                 return 0;
  141.                         csp->voidf = 1;
  142.                         return csp;
  143.                         }
  144.                 csp = csp->next;
  145.                 }
  146.         return 0;
  147. }
  148.  
  149.      scanexpr(node,duse)
  150. /*
  151.  *      scanexpr will scan the expression pointed to by node for optimizable
  152.  *      subexpressions. when an optimizable expression is found it is entered
  153.  *      into the tree. if a reference to an autocon node is scanned the
  154.  *      corresponding auto dereferenced node will be voided. duse should be
  155.  *      set if the expression will be dereferenced.
  156.  */
  157. struct enode    *node;
  158. int    duse;
  159. {       struct cse      *csp, *csp1;
  160.         if( node == 0 )
  161.                 return;
  162.         switch( node->nodetype ) {
  163.                 case en_icon:
  164.                 case en_labcon:
  165.                 case en_nacon:
  166.                         enternode(node,duse);
  167.                         break;
  168.                 case en_autocon:
  169.                         if( (csp = voidauto(node)) != 0 ) {
  170.                                 csp1 = enternode(node,duse);
  171.                                 csp1->uses = (csp1->duses += csp->uses);
  172.                                 }
  173.                         else
  174.                                 enternode(node,duse);
  175.                         break;
  176.                 case en_b_ref:
  177.                 case en_w_ref:
  178.                 case en_l_ref:
  179.                         if( node->v.p[0]->nodetype == en_autocon ) {
  180.                                 csp = enternode(node,duse);
  181.                                 if( csp->voidf )
  182.                                         scanexpr(node->v.p[0],1);
  183.                                 }
  184.                         else
  185.                                 scanexpr(node->v.p[0],1);
  186.                         break;
  187.                 case en_cbl:    case en_cwl:
  188.                 case en_cbw:    case en_uminus:
  189.                 case en_compl:  case en_ainc:
  190.                 case en_adec:   case en_not:
  191.                         scanexpr(node->v.p[0],duse);
  192.                         break;
  193.                 case en_asadd:  case en_assub:
  194.                 case en_add:    case en_sub:
  195.                         scanexpr(node->v.p[0],duse);
  196.                         scanexpr(node->v.p[1],duse);
  197.                         break;
  198.                 case en_mul:    case en_div:
  199.                 case en_lsh:    case en_rsh:
  200.                 case en_mod:    case en_and:
  201.                 case en_or:     case en_xor:
  202.                 case en_lor:    case en_land:
  203.                 case en_eq:     case en_ne:
  204.                 case en_gt:     case en_ge:
  205.                 case en_lt:     case en_le:
  206.                 case en_asmul:  case en_asdiv:
  207.                 case en_asmod:  case en_aslsh:
  208.                 case en_asrsh:  case en_asand:
  209.                 case en_asor:   case en_cond:
  210.                 case en_void:   case en_assign:
  211.                         scanexpr(node->v.p[0],0);
  212.                         scanexpr(node->v.p[1],0);
  213.                         break;
  214.                 case en_fcall:
  215.                         scanexpr(node->v.p[0],1);
  216.                         scanexpr(node->v.p[1],0);
  217.                         break;
  218.                 }
  219. }
  220.  
  221.      scan(blk)
  222. /*
  223.  *      scan will gather all optimizable expressions into the expression
  224.  *      list for a block of statements.
  225.  */
  226. struct snode    *blk;
  227. {       while( blk != 0 ) {
  228.                 switch( blk->stype ) {
  229.                         case st_return:
  230.                         case st_expr:
  231.                                 opt4(&blk->exp);
  232.                                 scanexpr(blk->exp,0);
  233.                                 break;
  234.                         case st_while:
  235.                         case st_do:
  236.                                 opt4(&blk->exp);
  237.                                 scanexpr(blk->exp,0);
  238.                                 scan(blk->s1);
  239.                                 break;
  240.                         case st_for:
  241.                                 opt4((struct enode **)&blk->label);
  242.                                 scanexpr((struct enode *)blk->label,0);
  243.                                 opt4(&blk->exp);
  244.                                 scanexpr(blk->exp,0);
  245.                                 scan(blk->s1);
  246.                                 opt4((struct enode **)&blk->s2);
  247.                                 scanexpr((struct enode *)blk->s2,0);
  248.                                 break;
  249.                         case st_if:
  250.                                 opt4(&blk->exp);
  251.                                 scanexpr(blk->exp,0);
  252.                                 scan(blk->s1);
  253.                                 scan(blk->s2);
  254.                                 break;
  255.                         case st_switch:
  256.                                 opt4(&blk->exp);
  257.                                 scanexpr(blk->exp,0);
  258.                                 scan(blk->s1);
  259.                                 break;
  260.                         case st_case:
  261.                                 scan(blk->s1);
  262.                                 break;
  263.                         }
  264.                 blk = blk->next;
  265.                 }
  266. }
  267.  
  268.      exchange(c1)
  269. /*
  270.  *      exchange will exchange the order of two expression entries
  271.  *      following c1 in the linked list.
  272.  */
  273. struct cse      **c1;
  274. {       struct cse      *csp1, *csp2;
  275.         csp1 = *c1;
  276.         csp2 = csp1->next;
  277.         csp1->next = csp2->next;
  278.         csp2->next = csp1;
  279.         *c1 = csp2;
  280. }
  281.  
  282. int     desire(csp)
  283. /*
  284.  *      returns the desirability of optimization for a subexpression.
  285.  */
  286. struct cse      *csp;
  287. {       if( csp->voidf || (csp->exp->nodetype == en_icon &&
  288.                         csp->exp->v.i < 16 && csp->exp->v.i >= 0))
  289.                 return 0;
  290.         if( lvalue(csp->exp) )
  291.                 return 2 * csp->uses;
  292.         return csp->uses;
  293. }
  294.  
  295. int     bsort(lst)
  296. /*
  297.  *      bsort implements a bubble sort on the expression list.
  298.  */
  299. struct cse      **lst;
  300. {       struct cse      *csp1, *csp2;
  301.         int             i;
  302.         csp1 = *lst;
  303.         if( csp1 == 0 || csp1->next == 0 )
  304.                 return 0;
  305.         i = bsort( &(csp1->next));
  306.         csp2 = csp1->next;
  307.         if( desire(csp1) < desire(csp2) ) {
  308.                 exchange(lst);
  309.                 return 1;
  310.                 }
  311.         return 0;
  312. }
  313.  
  314.      allocate()
  315. /*
  316.  *      allocate will allocate registers for the expressions that have
  317.  *      a high enough desirability.
  318.  */
  319. {       struct cse      *csp;
  320.         struct enode    *exptr;
  321.         int             datareg, addreg, mask, rmask;
  322.         struct amode    *ap, *ap2;
  323.         datareg = 3;
  324.         addreg = 10;
  325.         mask = 0;
  326.     rmask = 0;
  327.         while( bsort(&olist) );         /* sort the expression list */
  328.         csp = olist;
  329.         while( csp != 0 ) {
  330.                 if( desire(csp) < 3 )
  331.                         csp->reg = -1;
  332.                 else if( csp->duses > csp->uses / 4 && addreg < 14 )
  333.                         csp->reg = addreg++;
  334.                 else if( datareg < 8 )
  335.                         csp->reg = datareg++;
  336.                 else
  337.                         csp->reg = -1;
  338.                 if( csp->reg != -1 )
  339.                 {
  340.             rmask = rmask | (1 << (15 - csp->reg));
  341.                         mask = mask | (1 << csp->reg);
  342.                 }
  343.                 csp = csp->next;
  344.                 }
  345.         if( mask != 0 )
  346.                 gen_code(op_movem,4,make_mask(rmask),push);
  347.         save_mask = rmask;
  348.         csp = olist;
  349.         while( csp != 0 ) {
  350.                 if( csp->reg != -1 )
  351.                         {               /* see if preload needed */
  352.                         exptr = csp->exp;
  353.                         if( !lvalue(exptr) || (exptr->v.p[0]->v.i > 0) )
  354.                                 {
  355.                                 initstack();
  356.                                 ap = gen_expr(exptr,F_ALL,4);
  357.                                 if( csp->reg < 8 )
  358.                                         ap2 = makedreg(csp->reg);
  359.                                 else
  360.                                         ap2 = makeareg(csp->reg - 8);
  361.                                 gen_code(op_move,4,ap,ap2);
  362.                                 freeop(ap);
  363.                                 }
  364.                         }
  365.                 csp = csp->next;
  366.                 }
  367. }
  368.  
  369.      repexpr(node)
  370. /*
  371.  *      repexpr will replace all allocated references within an expression
  372.  *      with tempref nodes.
  373.  */
  374. struct enode    *node;
  375. {       struct cse      *csp;
  376.         if( node == 0 )
  377.                 return;
  378.         switch( node->nodetype ) {
  379.                 case en_icon:
  380.                 case en_nacon:
  381.                 case en_labcon:
  382.                 case en_autocon:
  383.                         if( (csp = searchnode(node)) != 0 )
  384.                                 if( csp->reg > 0 ) {
  385.                                         node->nodetype = en_tempref;
  386.                                         node->v.i = csp->reg;
  387.                                         }
  388.                         break;
  389.                 case en_b_ref:
  390.                 case en_w_ref:
  391.                 case en_l_ref:
  392.                         if( (csp = searchnode(node)) != 0 ) {
  393.                                 if( csp->reg > 0 ) {
  394.                                         node->nodetype = en_tempref;
  395.                                         node->v.i = csp->reg;
  396.                                         }
  397.                                 else
  398.                                         repexpr(node->v.p[0]);
  399.                                 }
  400.                         else
  401.                                 repexpr(node->v.p[0]);
  402.                         break;
  403.                 case en_cbl:    case en_cbw:
  404.                 case en_cwl:    case en_uminus:
  405.                 case en_not:    case en_compl:
  406.                 case en_ainc:   case en_adec:
  407.                         repexpr(node->v.p[0]);
  408.                         break;
  409.                 case en_add:    case en_sub:
  410.                 case en_mul:    case en_div:
  411.                 case en_mod:    case en_lsh:
  412.                 case en_rsh:    case en_and:
  413.                 case en_or:     case en_xor:
  414.                 case en_land:   case en_lor:
  415.                 case en_eq:     case en_ne:
  416.                 case en_lt:     case en_le:
  417.                 case en_gt:     case en_ge:
  418.                 case en_cond:   case en_void:
  419.                 case en_asadd:  case en_assub:
  420.                 case en_asmul:  case en_asdiv:
  421.                 case en_asor:   case en_asand:
  422.                 case en_asmod:  case en_aslsh:
  423.                 case en_asrsh:  case en_fcall:
  424.                 case en_assign:
  425.                         repexpr(node->v.p[0]);
  426.                         repexpr(node->v.p[1]);
  427.                         break;
  428.                 }
  429. }
  430.  
  431.      repcse(blk)
  432. /*
  433.  *      repcse will scan through a block of statements replacing the
  434.  *      optimized expressions with their temporary references.
  435.  */
  436. struct snode    *blk;
  437. {       while( blk != 0 ) {
  438.                 switch( blk->stype ) {
  439.                         case st_return:
  440.                         case st_expr:
  441.                                 repexpr(blk->exp);
  442.                                 break;
  443.                         case st_while:
  444.                         case st_do:
  445.                                 repexpr(blk->exp);
  446.                                 repcse(blk->s1);
  447.                                 break;
  448.                         case st_for:
  449.                                 repexpr((struct enode *)blk->label);
  450.                                 repexpr(blk->exp);
  451.                                 repcse(blk->s1);
  452.                                 repexpr((struct enode *)blk->s2);
  453.                                 break;
  454.                         case st_if:
  455.                                 repexpr(blk->exp);
  456.                                 repcse(blk->s1);
  457.                                 repcse(blk->s2);
  458.                                 break;
  459.                         case st_switch:
  460.                                 repexpr(blk->exp);
  461.                                 repcse(blk->s1);
  462.                                 break;
  463.                         case st_case:
  464.                                 repcse(blk->s1);
  465.                                 break;
  466.                         }
  467.                 blk = blk->next;
  468.                 }
  469. }
  470.  
  471.      opt1(blk)
  472. /*
  473.  *      opt1 is the externally callable optimization routine. it will
  474.  *      collect and allocate common subexpressions and substitute the
  475.  *      tempref for all occurrances of the expression within the block.
  476.  *
  477.  *        optimizer is currently turned off...
  478.  */
  479. struct snode    *blk;
  480. {
  481.         olist = 0;
  482.         scan(blk);            /* collect expressions */
  483.         allocate();             /* allocate registers */
  484.         repcse(blk);          /* replace allocated expressions */
  485. }
  486.